\documentclass[a4paper,11pt]{article}
\usepackage{graphicx}
\usepackage{float}
%\usepackage{mathdesign}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{booktabs}
\usepackage{listings}
\usepackage{hyperref}
\usepackage{multirow}
%\usepackage[default,light]{sourcesanspro}
\usepackage[default]{sourcesanspro}
\usepackage[scale=0.7,defaultmono]{droidmono}
\usepackage[charter]{mathdesign}
%\usepackage[T1]{fontenc}
\usepackage[usenames,dvipsnames,svgnames,table]{xcolor}
%\documentclass[a4paper,11pt]{scrartcl}
%\usepackage{pala}
%\linespread{1.05}     % Palatino needs more leading (space between lines)
%\usepackage[T1]{fontenc}
%\usepackage{xltxtra}
%\setromanfont[Mapping=tex-text]{Linux Libertine O}
% \setsansfont[Mapping=tex-text]{DejaVu Sans}
% \setmonofont[Mapping=tex-text]{DejaVu Sans Mono}
%\usepackage[margin=1.0in]{geometry}
%\usepackage[adobe-utopia]{mathdesign}
%\usepackage{fourier}
%\usepackage[default,sfdefault,light,t1]{sourcesanspro}
%\usepackage{tgpagella}    
%\usepackage[scaled]{beramono}
%\usepackage[default,nosfdefault,semibold,t1]{sourcesanspro}
%\usepackage{sfmath}
%\DeclareMathOperator*{\lcm}{lcm}
%\DeclareMathOperator*{\Prob}{Prob}
%\def\verbatim{\small\@verbatim \frenchspacing\@vobeyspaces \@xverbatim}
%\def\texttt{\small\texttt}
%\setmonofont[Scale=0.95]{droidmono}

%set margins
\addtolength{\oddsidemargin}{-.875in}
\addtolength{\evensidemargin}{-.875in}
\addtolength{\textwidth}{1.75in}

\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\title{CUDA-Squeeze%\\\color{gray}Final Draft Copy}
}
%\author{
%Benjamin Hugo\\
%    \affaddr{Department of Computer Science}\\
%    \affaddr{University of Cape Town}\\
%    \email{bhugo@cs.uct.ac.za}
%    }\author{
%Brandon Talbot\\
%    \affaddr{Department of Computer Science}\\
%    \affaddr{University of Cape Town}\\
%    \email{btalbot@cs.uct.ac.za}}\author{
%Heinrich Strauss\\
%    \affaddr{Department of Computer Science}\\
%    \affaddr{University of Cape Town}\\
%    \email{hstrauss@cs.uct.ac.za}
%}
\author{
 \textbf{Benjamin Hugo}\\
 \small{Department of Computer Science}\\
 \small{University of Cape Town}\\
 \small\texttt{bhugo@cs.uct.ac.za}
 \and
 \textbf{Brandon Talbot}\\
 \small{Department of Computer Science}\\
 \small{University of Cape Town}\\
 \small\texttt{btalbot@cs.uct.ac.za}
 \and
 \textbf{Heinrich Strauss}\\
 \small{Department of Computer Science}\\
 \small{University of Cape Town}\\
 \small\texttt{hstrauss@cs.uct.ac.za}
}

\date{10 June 2013}
\newcommand\VRule[1][\arrayrulewidth]{\vrule width #1}
%\maketitle
%\makeindex
\begin{document}
%$\ttfontfamily{cmtt}\selectfont 
%\ttfontfamily{droidmono}
%\renewcommand{\ttdefault}{blg}
%\begin{table*}
%\begin{tabular}{rl}%[width=0.75\pagewidth]{rl}
%\begin{figure*}[h]
%\includegraphics[width=0.4\textwidth]{fp-logo-bl.png}
%\end{figure*} 
%\begin{figure*}%[h!]
%\includegraphics[width=0.4\textwidth]{fp-logo-br.png}
%\end{figure*}
%\\
 
%\end{tabular}\end{table*}
\maketitle
 \begin{center}
%\huge{CUDA-Squeeze}\\
   \begin{minipage}{0.25\linewidth}
     \begin{figure}[H]
       \includegraphics[width=\linewidth]{fp-logo-tl.png}
       %\caption{This is the first figure}
     \end{figure}
   \end{minipage}
   \hspace{0.05\linewidth}
   \begin{minipage}{0.25\linewidth}
     \begin{figure}[H]
       \includegraphics[width=\linewidth]{fp-logo-tr.png}
       %\caption{This is the second figure}
     \end{figure} 
   \end{minipage}\linebreak
   % \\
   \begin{minipage}{0.25\linewidth}
     \begin{figure}[H]
       \includegraphics[width=\linewidth]{fp-logo-bl.png}
       %\caption{This is the first figure}
     \end{figure}
   \end{minipage}
   \hspace{0.05\linewidth}
   \begin{minipage}{0.25\linewidth}
     \begin{figure}[H]
       \includegraphics[width=\linewidth]{fp-logo-br.png}
       %\caption{This is the second figure}
     \end{figure}
   \end{minipage}
   \end{center}
\pagebreak
%\toc
%\pagebreak
\section{Project Description}

The SKA (Square Kilometer Array) South Africa requires a compression algorithm that offers reasonable compression
ratios, as well as being fast enough to keep up with the antenna output rates. This need arrises due
to the requirement of saving streaming data onto a storage system and reading queries from that system
simultaneously. This is where the focus of our project lies. We will be taking streaming data from correlators 
and beamformers (which combines pairs of data channels from the antennae) and compress the data-stream using GPGPU 
(General-Purpose Computing on Graphical Processing Units) in order to achieve the
speeds that SKA requires, while maintaining reasonable compression ratios. Refer to Figure \ref{figuredatapipeline} for an overview
of the data pipeline. 

\begin{figure}[h!]
\includegraphics[width=1.0\textwidth]{Process.png}
\caption{Simplified overview of the SKA data pipeline}\label{figuredatapipeline}
\label{Process}
\end{figure}

%\section{}

CUDA-Squeeze is a scientific experiment to test which compression method run on an optimised CPU- or GPU-code base would be the
most efficient for the frequency data produced by the SKA radio telescope array. We will be testing $3$ different types of algorithms
between the $3$ team members. For each of the algorithms we will be creating a CPU (Central Processing Unit) P-Threaded (Processor Thread)
version of the algorithm  with optimizations for SSE and AVX and a GPU-based algorithm. We will
then
determine if the GPU-based versions have the required speedup factor. Finally we will 
determine which of
the $3$ algorithms is best suited to SKA's intended purpose of real-time, in-path data compression and decompression.
\subsection{Problem Statement}

The sample rate of the incoming $32$-bit floating-point data is expected to be in excess of $15$~terabits per second
for the KAT-$7$ array alone. This sample rate has a quadratic growth rate as the number of dishes is increased
(since the input data is correlated between pairs of antennae). We are testing the feasibility of using a
highly multithreaded coprocessor such as GPU to perform bulk real-time compression where realtime data
throughput enjoys priority over excellent compression ratios. Due to this quadratic growth rate even a small
percentage saving will have a significant impact on I/O capacity, both in terms of transfer rates and storage
capacity. Our stated goal is to determine whether this is possible, given the nature of the data.
\section{Procedures and Methods}

\subsection{Predictive Methods}
Predictive methods use a predictor function to attempt to predict what the next value would be. They tend to use
two or more of the previous values to determine what the next value could be. The algorithms then find the
difference between the predicted value and the actual value for the next number. Knowing how many zeroes
before the initial one in the binary representation means they can shorten those zeroes by encoding them
as a run-length encoder would, if run on that sequence.

This means that for data that has many values that are close to each other, we could achieve a very
good compression ratio. A problem arises if the data has huge differences and spikes that ends up either not
compressing at all or actually increasing the size of the data.

SKA has said their data will mainly low values very close to each other, and there should be very few
spikes in the numbers. This means that predictive methods are viable for our circumstances.

Additionally, floating-point numbers are not denormalized at any point in the processing pipeline,
yielding a consistent number format. This will improve the predictability of the data.

%{\color{red}\subsection{Adaptive Arithmetic Coding}

%In general arithmetic coding uses a probability distribution to assign real-valued sub-intervals of [0,1) for every symbol it encodes. These sub-intervals are proportional to the symbol's probability of occurrence. The method reduces the difference between the entropy of the uncompressed encoding and the optimal encoding of the data (known as the measurement of redundancy).

%It is one of the most widely used variable length encoding schemes and is applicable in our case, because small floating point values can be encoded to use significantly less bits per value than the standard $32$-bit encoding scheme. In our case the probability distribution function will have to be estimated because doing a double pass over the data may be infeasible.
%}
\subsection{Adaptive Huffman Coding}
Huffman coding allocates codes to each unique value in the data, this code being shorter (smaller)
than the value it is allocated to. It creates a table that stores the codes allocated to the specified value.
It allocates a shorter code to the most commonly seen value in the data.

Once it has created all the codes for all unique values in the file, it replaces the value with the code,
thus shortening (compressing) the data. It also stores the table in the beginning in order for it to decompress the data.

Huffman coding is seen in many aspects of compression. The most common of these compression algorithms being video compression algorithms, in conjunction with DXT trees.

\subsection{Zero-Length Encoding}
Zero-Length Encoding is basically run-length encoding, just performed on the binary representation of data.
In Zero-Length Encoding you run through the data and replace sections of the binary stream where there are
multiple $0$s or $1$s with the number of repetitions and what is repeating, Eg. $1000001$ becomes $1(5)01$. where
the $(5)$ is a tag to say it is a number representation and the $5$ to tell how many $0$s there are.

This is a viable option because the data samples we receive are skewed towards the least-significant bits.
Most of the time they will be fairly small numbers and therefore will not use many of the mantissa bits. Values
that cannot be fitted into $32$-bits are flagged as unusable in the context of radio astronomy (these spikes are
for the most part caused by ground-based or satellite interference), so these are excluded from compression
in most cases.

\subsection{Data Throughput}

Data throughput through the processing pipeline will be a limiting factor. At present, commodity hardware
allows for around $16$~gigabits per second (per direction) across the PCI Express Bus (theoretical). With data
rates per antenna approaching $2$~terabits/s, there will likely not be enough available bandwidth to read the
data in real-time. This is noted as a potential risk to the project. Future hardware evolution may negate
this concern.
%{\color{red} Current flagship commodity Intel mainboards have not significantly improved the bandwidth
%across the PCIe bus. InfiniBand network switches from QLogic have an aggregated theoretical $51$~terabits per
%second over $864$ network ports, but are prohibitively expensive and require large infrastructure fan-out. The
%CI Express $4.0$ standard recently announced allows for $32$~gigabits per second bi-directionally, but this is
%still quite low for our purposes unless multiplexed.}

The stated aim is to process the data at a line-rate of $90\%$ of $40$~gigabits per second, as that is the network I/O rate at the Compute Nodes. 
It is, however, unlikely that these rates will be sustained for a significant time
during a single astronomical observation.

We intend to perform testing on hardware in the Honours laboratory and, potentially, the compute clusters available. The Lab hardware is based on commodity-hardware, generally an Intel~DQ$57$TML mainboard,
using the onboard Intel~$82578$DM $1$ gigabit per second NIC.  
The data will be processed through a Quad-Core
Intel Core~i$3$ or i$5$ $3.00$~GHz processor and GPU tasks will be offloaded to a CUDA Compute~$2.0$ capable device,
generally an nVidia GeForce~GTX~$560$~Ti or equivalently equipped machine.
While the available bandwidth across the PCI Express bus is high in comparison to the rest of the hardware, we need to efficiently transfer that to the GPU in chunks of $1-3$~gibibytes, due to current hardware
limitations. This will likely introduce latency into the computation pipeline, which we will have to mitigate
as best possible.

As part of the GPGPU processing paradigm, technologies are currently being developed to transfer data directly from
I/O devices to the GPU to bypass the throughput deterioration through the mainboard RAM. These technologies are not yet commercially available.
Addressing the data-throughput issues arising from these should, therefore, be considered outside the scope of our proposal.

Given that the data rate needs to approach $40$~gigabits per second, reading from Hard-Disk or Network Interface Card will not be enough to 
keep data buffers full. We will therefore read the data from disk into Host memory and compress permutations along Floating-Point boundaries to ``randomize'' the input.
This will allow for the highest data-throughput rate to the CPU and GPU, where the compression rates will be benchmarked.

We may assume that data-errors do not occur, since ECC RAM is used everywhere within the Compute Nodes, as stated by the SKA Office.

We do not consider the speed of the disk subsystem in this project, as this will be handled outside of the input and output streams for our implementations.
As such, storage and database storage components are a specific exclusion to this project.

\subsection{Testing and Evaluation Methods}
A few samples of raw data (in $1-3$~gibibyte blocks) will be run through each CPU and GPU implementation of
each algorithm.
This will give us the compression ratio \textit{compressed data}:\textit{uncompressed data}. This will be used to gauge the improvement of the algorithm over raw throughput for data storage.
More importantly, the algorithm has to run at real-time rates. This will be evaluated by subtracting the
time to copy data to and from the system memory from the time to execute the execution run in entirety.
\subsection{Ethical, Professional and Legal Issues}

The sample data will remain intellectual property of the SKA. There are no known U.S. or international patent
restrictions on the methods we mentioned above. No ethics clearance will be required for our project.

\subsection{Related Work}
The zero-length compression scheme we described has been used successfully employed by Abadi et al. \cite{Abadi:2006:ICE:1142473.1142548}
to reduce database sizes, under similar circumstances (where the run-lengths of leading zeroes is sufficiently
large to truncate normal $4$ byte-integer values down to $3$ or fewer bytes).

The predictive methods described by O'Neil et al. \cite{O'Neil:2011:FDC:1964179.1964189} and Ratanaworabhan et al. \cite{4976448} are
two parallel implementations of $64$-bit double compression that will work on chunks of streaming data. The GFC algorithm
specified by O'Neil achieves $75$~gigabits per second but trades compression ratios for speed, where the parallel FPC compressor 
achieves much better compression ratios at half less than half that speed. However,
the FPC compressor uses a lookup table to predict, which makes it too memory intensive for our purposes.

Huffman coding is a well-researched technique, used in many contemporary compression implementations.
 Knuth\cite{knuth1985dynamic} and Gallagher\cite{gallager1978variations} independently suggested various ways of localising the Huffman
lookup-table, and Vitter\cite{vitter1987design} shows that the lookup size is bounded by a factor of two and that incrementing or decrementing
the lookup-table indices can be accomplished in $O({1})$\cite{bentley1986locally}.
This implies that a compression factor would likely be established for Adaptive Huffman Coding, even with a single pass.

%{\color{red}\subsection{Anticipated Outcomes}}

%We expect {\color{red}...}

\subsection{Dynamic Algorithm Selection}
Should the compression rates be different between different kinds of observation,
it would be useful to SKA South Africa to dynamically select the compression algorithm based on observed data.

The feasibility study for this is considered an inclusion in the scope of our project.

\subsection{Altera OpenCL compiler}
Altera, the FPGA hardware vendor, have plans to introduce an OpenCL compiler to program the FPGAs in use by SKA.
This would unify their code-base and they will investigate this once it becomes available.

This, and the associated OpenCL implementation, is considered outside the scope of our project.

\section{Project Plan}

\subsection{Deliverables}

There are several major milestones in our project. They primarily consist of building $3$ viable GPU-based
compressors and $3$ multi-threaded CPU implementations to use as a baseline in further analysis. The basic CPU
versions will serve as a judgement of the feasibility of the undertaking and has to be completed by the $1^\mathrm{st}$ of July.
Work on optimization will be undertaken while developing the basic CPU versions and will be due by the $30^\mathrm{th}$ of July.
Work on the GPU implementations will commence after the individual literature surveys have been expanded
and some initial architecture and experimental designs have been established. The GPU versions will require a
significant investment of time and profiling to optimise and will run throughout much of the second
semester. We will be testing our solutions concurrently, as well as documenting the required results. These
will range from unit testing to profiling. The final comparison writeup is due on the $25^\mathrm{th}$ of September. In
this we hope to combine our primary results in terms of compression throughput and ratios. See the Gantt
chart (Figure \ref{figureganttchart}) for the other less significant deliverables.

\begin{figure}[h!]
\includegraphics[width=1.0\textwidth]{final_project_gantt.png}
\caption{Project Timeline and Deliverables}\label{figureganttchart}
\end{figure}

\subsection{Work Allocation}

At the end of the project we expect to have both GPU-based and P-Threaded (CPU) versions (SSE- and AVX-optimised, where applicable) of the following
algorithms:

\begin{itemize}
\item \textbf{Implementation of a GFC predictor:} to be investigated by \textit{Benjamin Hugo}
\item \textbf{Parallel block-based Huffman coding:} to be investigated by \textit{Brandon Talbot}
\item \textbf{Zero-Length Encoding:} to be investigated by \textit{Heinrich Strauss}
\end{itemize}

One of the major design issues is deciding on how to divide the data up per graphics card, where we are
limited in terms of L$1$ cache size and data transfer rates through the PCI-Express bus. These constraints
play a major role in achieving any significant speedup from the GPU.

We will compare performance between the $3$ algorithms in terms of throughput, memory usage
and compression ratios. These results will determine whether it is feasible to use GPUs as compression co-processors
in the data cluster.

The project will be deemed successful if we can determine which one of the basic algorithms is a good
candidate for compression on a co-processor or whether moving the compression onto a co-processor is feasible. 
Our focus is specifically on the compression itself on a single co-processor without consideration of
scaling this over multiple nodes.
\subsection{Technical Resources}

The GPU implementations will be run on CUDA compute capability >$2.0$ devices, such as those found in the
CS Honours laboratory. It will be preferable to run the profiling on the systems with higher capability in terms
of number of CPU cores and newer CUDA compute capabilities, such as the ICTS HEX compute cluster or the
Center for High Performance Computing cluster.

Obtaining enough raw testing data should not considered an issue. The SKA Office have committed to
providing us with very large samples (in excess of $100$ gibibytes, if necessary).

\subsection{Human Resources}
Associate-Professor~James Gain and Dr.~Patrick Marais will co-supervise our project. They have co-authored
several papers on compression schemes including compression on irregularly sampled height-fields, point
clouds and molecular dynamics trajectory files.

Jason Manley is a Digital Design Engineer and Digital Signal Processing specialist at the SKA office in
Pinelands. Jason has provided valuable insight into the SKA architecture and serves as our external advisor.
Jason has kindly agreed to provide the sample data for our experiment.
\subsection{Risks and Mitigation}

%\begin{tabular}{|c|c|c|c|}
%\hline
%Impact/Likelihood & low & medium & high \\
%\hline
%low & & & \\
%\hline
%medium & Benchmarking resources & & Implementation & Optimisations \\
%\hline
%high & & & \\
%\hline
%\caption{Risk Matrix (Impact vs. Likelihood)}
%\end{tabular}
We consider the complexity of implementation and optimization as the biggest risk to our project. As already
mentioned the project is divided into $3$ separate algorithm implementations. Each implementation will have
its own CPU baseline written to which comparisons can be drawn. This ensures that the project is loosely
coupled and that failure in some of the components can be tolerated.

The Risk Matrix (Figure \ref{tableriskmatrix}) for the project is as follows:

%\begin{table}[h]\footnotesize
%\begin{center}
%\caption{Risk Matrix}
%\begin{tabular}{|c||c|c|c|}
%\hline
%Impact/Likelihood & \textbf{low} & \textbf{medium} & \textbf{high} \\
%\hline
%\hline
%\textbf{low} & Benchmarking resources & & \\
%\hline
%\textbf{medium} & & Implementation & Optimisations \\
%\hline
%\textbf{high} & & & \\
%\hline
%\end{tabular}
%\caption{Risk Matrix (Impact vs. Likelihood)}
%\end{center}
%\end{table}

%\begin{center}
%\begin{tabular}{cccc}
% 1 & 2 & 3 \\
% 4 & 5 & 6 \\
% 7 & 8 & 9
 
%\end{tabular} 
%\caption{a table}
%\end{center} 

%\begin{table}[h]\small\begin{center}
%\begin{tabular}{ccc|c|c|cl}
%\cline{3-5}
%& & \multicolumn{3}{ c }{\textit{likelihood}} \\ \cline{3-5}
%& & \textbf{low} & \textbf{medium}& \textbf{high}\\ \cline{1-5} \cline{3-5}
%\multicolumn{1}{ c }{\multirow{3}{*}{\textit{impact}} } &
%\multicolumn{1}{ c }{\textbf{low}} & Benchmarking Resources  &  &       \\ \cline{2-5}
%\multicolumn{1}{ c  }{}                        &
%\multicolumn{1}{ c }{\textbf{medium}} &  & Implementation & Optimisation \\ \cline{2-5}
%\multicolumn{1}{ c  }{}                        &
%\multicolumn{1}{ c }{\textbf{high}} &  &  &   \\ \cline{1-5}
%\end{tabular}\caption{Risk Matrix (Impact vs. Likelihood)}\label{tableriskmatrix}
%\end{center}
%\end{table}

%\begin{tabular}{llr}
%\toprule
%\multicolumn{2}{c}{Name} \\
%\cmidrule(r){1-2}
%First name & Last Name & Grade \\
%\midrule
%John & Doe & $7.5$ \\
%Richard & Miles & $2$ \\
%\bottomrule
%\end{tabular}


%\definecolor{TableBorder}{rgb}{0.0078,0.6824,0.7882}
%\definecolor{TableEven}{rgb}{0.8000,0.9216,0.9490}
%\definecolor{TableOdd}{rgb}{1,1,1}

%\rowcolors{2}{TableEven}{TableOdd}

%\begin{tabular}{
%!{\color{TableBorder}\VRule[1pt]} l
%l
%!{\color{TableBorder}\VRule[2pt]} r
%!{\color{TableBorder}\vline} r
%!{\color{TableBorder}\vline} r
%!{\color{TableBorder}\VRule[1pt]}}

%\arrayrulecolor{TableBorder}\specialrule{1pt}{0pt}{0pt}

%\rowcolor{TableOdd}
%& & Data & Spot. & Reg. \\ \specialrule{2pt}{0pt}{0pt}
%Avg. temp. & [$^\circ$C] & $21.5$ & $21.6$ &    $21.7$ \\ \hline
%Avg. pwr.& [W] & $732$ &    $738$ & $746$  \\ \hline
%Avg. spot. &[DKK/MWh] & $374$   & $295$ &   $289$ \\ \hline
%Total cost& [DKK] & $2.398$ & $2.009$ & $1.970$  \\ \hline
%Savings& [$\%$] & $0$   & $16.2$ & $17.8$ \\
%\specialrule{1pt}{0pt}{0pt}
%\end{tabular}
%\begin{table}[h]\small\begin{center}
%\begin{tabular}{rlll}
%& \multicolumn{3}{c}{\textbf{likelihood}} \\ %\toprule
%& low & medium & high \\ %\hline
%\cmidrule(l){2-4}
%\multirow{3}{*}{risk} 
%low &\vline Benchmarking Resources &\vline &\vline \\ %\cmidrule(r){2-4}
%\textbf{impact}$\quad$medium &\vline  &\vline Implementation &\vline Optimisation\\%\cmidrule(r){2-4}
%high &\vline  &\vline  &\vline  \\ %\cmidrule(r){2-4}%\bottomrule
%\end{tabular}\caption{Risk Matrix (Impact vs. Likelihood)}\label{tableriskmatrix2}
%\end{center}
%\end{table}
%\begin{table}[h]\small\begin{center}
\begin{figure}[h!]
\includegraphics[width=0.8\textwidth]{risk_matrix.png}
\caption{Risk Matrix (Impact vs. Likelihood)}\label{tableriskmatrix}\end{figure}
% \end{center}
%\end{table}


There is some technical risk to the project. Although there is sufficient hardware resources within the
Honours laboratory for the scope of development, any comparison and benchmarking will require access to
machines with larger capability in terms of CPU cores and GPUs with higher capacity, such as those provided on
the ``HEX'' HPC cluster. Additional resources can be provided by the SKA Office, as they have communal compute nodes
available at their offices in Pinelands. These resources will be arranged
well ahead of analysis, and if they cannot be obtained we will perform benchmarking using the hardware we
have at our disposal.
\pagebreak\section{Glossary}
\begin{itemize}
\item {\textbf{AVX} - Advanced Vector Extensions; an extension to the Intel architecture implemented in Intel Sandy-Bridge and newer processors. 
The SIMD registers' sizes are expanded to $256$ bits, instead of the $128$-bit registers found in SSE. Requires a recent operating system to utilize (Windows $7$+; Linux $2.6.30$+; MacOS $10.6.8$+).}
\item {\textbf{Compression ratio} - compressed size / uncompressed size.}
\item {\textbf{CPU} - Central Processing Unit}
\item {\textbf{DXT Tree} - \color{black}A data-structure used in lossy compression derived from S3 Texture Compression for GPUs.}
\item {\textbf{Entropy} - (Information Theory) Entropy is the measurement of the information contained in a single base-$n$ symbol (as transmitted per time unit by some source)\cite[p. 46 - 47]{salomon2004data}}
\item {\textbf{Gibibytes} - A measure of data size, using the binary-prefix definition of Giga-; $2^{30}$ bytes.}
\item {\textbf{Gigabits per second} - A measure of throughput speed, using the SI definition of Giga-; $10^9$ bits per second.}
\item {\textbf{GPGPU} - General-Purpose computing on Graphical Processing Units}
\item {\textbf{GPU} - Graphical Processing Unit}
\item {\textbf{L1 Cache} - Level $1$ Cache; In the Intel x$86$ architecture, the fastest, but smallest, CPU cache memory.}
\item {\textbf{KAT / KAT-7} - A $7$-dish Radio Telescope Array in the Northern Cape, ZA}
\item {\textbf{MeerKAT} - A proposed $64$-dish Radio Telescope Array planned for completion by $2016$}
\item {\textbf{P-Thread} - Processor Thread}
\item {\textbf{Real-time Rates} - For the purposes of this project, being able to attain over $36$~gigabits per second is considered ``real-time''}
\item {\textbf{Redundancy} - (Information Theory) The difference between the largest possible entropy of a symbol set and its actual entropy. Mathematically redundancy is defined 
as follows ($n$ is the size of a symbol set and $P_i$ is the probability that a symbol $c_i$ is transmitted from a source)\cite[p. 46 - 47]{salomon2004data}:
\begin{equation*}
 R = \log_2n + \sum_1^nP_i\log_2P_i
\end{equation*}}
\item {\textbf{SKA} - Square Kilometer Array, the largest radio-telescope array in the Southern Hemisphere (over $3000$ dishes) planned for first-operation in $2020$.}

\item {\textbf{SSE} - Streaming SIMD Extensions; A set of additional instructions introduced to Intel processors from the 
Pentium~$3$ onwards which allows the same instruction to be performed on multiple data targets, thus improving performance of an optimised program.}
\end{itemize}

\bibliographystyle{siam}
\pagebreak\bibliography{ResearchProposal-CUDA-Squeeze}

\end{document}
